package ticketingsystem;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

public class TicketingDS implements TicketingSystem {
	private final Route[] routes;
	private final int seatNum;
	private final DistHistory history;
	private final int threadNum;
	private final AtomicInteger threadCounter;
	private final TID nextTid;
	static final int hisSize = 16;
	static boolean heatUp = true;

    public TicketingDS(int routeNum, int coachNum, int seatNum, int stationNum, int threadNum) {
		if(heatUp){
			heatUp = false;
			Test.singleTest(threadNum, false);
			Test.singleTest(threadNum, false);
		}
		this.seatNum = seatNum;
		this.threadNum = threadNum;
		nextTid = new TID();
		routes = new Route[routeNum];
		threadCounter = new AtomicInteger(0);
		history = new DistHistory();
		for (int i = 0; i < routeNum; i++) {
			routes[i] = new Route(coachNum * seatNum, stationNum);
		}
    }


    public Ticket buyTicket(String passenger, int route, int departure, int arrival) {
		if(route > routes.length || arrival <= departure) return null;

		int result = routes[route - 1].buyTicket(bitmap(departure, arrival));
		if(result >= 0){
			MyTicket ticket = new MyTicket();
			ticket.tid = nextTid.getAndIncrement();
			ticket.passenger = passenger;
			ticket.route = route;
			ticket.coach = (result / seatNum) + 1;
			ticket.seat = (result % seatNum) + 1;
			ticket.departure = departure;
			ticket.arrival = arrival;
			history.set((int) ticket.tid, ticket);
			return ticket;
		}
        return null;
    }


    public int inquiry(int route, int departure, int arrival) {
        return routes[route - 1].inquiry(bitmap(departure, arrival));
    }


    public boolean refundTicket(Ticket ticket) {
		AtomicReference<MyTicket> hisRef = history.get((int) ticket.tid);
		MyTicket t;
		if(hisRef == null || (t = hisRef.get()) == null || !t.equals(ticket) || !hisRef.compareAndSet(t, null)) return false;
		routes[ticket.route - 1].refundTicket((ticket.coach - 1) * seatNum + ticket.seat - 1, bitmap(ticket.departure, ticket.arrival));
		return true;
    }

    private class Route {
        AtomicInteger[] allSeat;
        AtomicInteger allocated;

        Route(int seatNum, int stationNum) {
            allSeat = new AtomicInteger[seatNum];
            allocated = new AtomicInteger(0);
            int emptySeat = bitmap(stationNum);
            for (int i = 0; i < allSeat.length; i++) {
                allSeat[i] = new AtomicInteger(emptySeat);
            }
        }

        public int buyTicket(int target) {
            int i = 0;
            int end = allocated.get();
            int seat;
            while (i < allSeat.length) {
                if (i >= end) end = allocated.get();
				if (i >= end) end = allocated.updateAndGet(j -> j + threadNum);
				// if (i >= end) end = allocated.incrementAndGet();
                while (target == ((seat = allSeat[i].get()) & target)) {
                    if (allSeat[i].compareAndSet(seat, seat & ~target)) return i;
                }
                i++;
            }
            return -1;
        }


        public int inquiry(int target) {
            int count = 0;
            int end = Math.min(allocated.get(), allSeat.length);
            for (int i = 0; i < end; i++) {
                if ((allSeat[i].get() & target) == target) count++;
            }
            return allSeat.length - end + count;
        }


        public void refundTicket(int seat, int target) {
            while (true) {
                int old = allSeat[seat].get();
                if (allSeat[seat].compareAndSet(old, old | target)) return;
            }
        }
    }

	private class DistHistory{
		private final History[] history;
		DistHistory(){
			this.history = new History[threadNum];
			for(int i=0; i<threadNum; i++){
				history[i] = new History();
			}
		}
		AtomicReference<MyTicket> get(int index){
			return history[index%threadNum].get(index/threadNum);
		}
		void set(int index, MyTicket ticket){
			history[index%threadNum].set(index/threadNum, ticket);
		}
	}

	private static class History{
		private final AtomicReference<MyTicket>[] history;
		private History next;
		@SuppressWarnings("unchecked")
		History(){
			history = new AtomicReference[1<<hisSize];
		}
		private History getNext(){
			while(next == null){
				next = new History();
			}
			return next;
		}
		AtomicReference<MyTicket> get(int index){
			if(index < history.length) return history[index];
			else if(next != null) return next.get(index - history.length);
			else return null;
		}
		void set(int index, MyTicket ticket){
			if(index < history.length) history[index] = new AtomicReference<>(ticket.clone());
			else getNext().set(index - history.length, ticket);
		}
	}

	private static class MyTicket extends Ticket implements Cloneable{

		@Override
		public MyTicket clone() {
			try {
				return (MyTicket) super.clone();
			} catch (CloneNotSupportedException e) {
				throw new AssertionError();
			}
		}

		boolean equals(Ticket t){
			return this.tid == t.tid &&
					this.passenger.equals(t.passenger)&&
					this.route == t.route&&
					this.coach == t.coach&&
					this.seat  == t.seat &&
					this.departure == t.departure&&
					this.arrival == t.arrival;
		}
	}

	private class TID extends ThreadLocal<Long>{
		@Override
		protected Long initialValue(){
			// return new Long((long)threadCounter.getAndIncrement());
			int val = threadCounter.getAndIncrement();
			if(val >= threadNum) throw new RuntimeException("Too many threads");
			return (long) val;
		}

		Long getAndIncrement(){
			try{return this.get();} 
			finally{this.set(this.get()+threadNum);}
		}
	}

    private static int bitmap(int station) {
        return (1 << (station - 1)) - 1;
    }

    private static int bitmap(int departure, int arrival) {
        return bitmap(arrival) ^ bitmap(departure);
    }

    public boolean buyTicketReplay(Ticket ticket) {
        return false;
    }
    public boolean refundTicketReplay(Ticket ticket) {
        return false;
    }

}
